package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//递归20ms 60%, 6.8MB 49%
func isSubStructure(A *TreeNode, B *TreeNode) bool {
	var recur func(*TreeNode, *TreeNode) bool
	recur = func(A *TreeNode, B *TreeNode) bool {
		if B == nil {
			return true
		}
		if A == nil || A.Val != B.Val {
			return false
		}
		return recur(A.Left, B.Left) && recur(A.Right, B.Right)
	}

	return (A != nil && B != nil) && (recur(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B))

}

func main() {
	fmt.Println(isSubStructure(&TreeNode{}, &TreeNode{}))
}
